/*-------------------------------------------------------------------------
 *
 * gistscan.c
 *	  管理GiST索引关系扫描的例程
 *
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * IDENTIFICATION
 *	  src/backend/access/gist/gistscan.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "access/gist_private.h"
#include "access/gistscan.h"
#include "access/relscan.h"
#include "utils/float.h"
#include "utils/lsyscache.h"
#include "utils/memutils.h"
#include "utils/rel.h"


/* 成对堆比较函数用于 GISTSearchItem 队列 */
static int fc_pairingheap_GISTSearchItem_cmp(const pairingheap_node *fc_a, const pairingheap_node *fc_b, void *fc_arg)
{
	const GISTSearchItem *fc_sa = (const GISTSearchItem *) fc_a;
	const GISTSearchItem *fc_sb = (const GISTSearchItem *) fc_b;
	IndexScanDesc fc_scan = (IndexScanDesc) fc_arg;
	int			fc_i;

	/* 按照距离比较进行排序 */
	for (fc_i = 0; fc_i < fc_scan->numberOfOrderBys; fc_i++)
	{
		if (fc_sa->distances[fc_i].isnull)
		{
			if (!fc_sb->distances[fc_i].isnull)
				return -1;
		}
		else if (fc_sb->distances[fc_i].isnull)
		{
			return 1;
		}
		else
		{
			int			fc_cmp = -float8_cmp_internal(fc_sa->distances[fc_i].value,
												   fc_sb->distances[fc_i].value);

			if (fc_cmp != 0)
				return fc_cmp;
		}
	}

	/* 堆项目在内部页面之前，以确保深度优先搜索 */
	if (GISTSearchItemIsHeap(*fc_sa) && !GISTSearchItemIsHeap(*fc_sb))
		return 1;
	if (!GISTSearchItemIsHeap(*fc_sa) && GISTSearchItemIsHeap(*fc_sb))
		return -1;

	return 0;
}


/* 用于扫描 GiST 索引的 Index AM API 函数 */

IndexScanDesc gistbeginscan(Relation fc_r, int fc_nkeys, int fc_norderbys)
{
	IndexScanDesc fc_scan;
	GISTSTATE  *fc_giststate;
	GISTScanOpaque fc_so;
	MemoryContext fc_oldCxt;

	fc_scan = RelationGetIndexScan(fc_r, fc_nkeys, fc_norderbys);

	/* 首先，设置一个带有扫描生命周期内存上下文的 GISTSTATE */
	fc_giststate = initGISTstate(fc_scan->indexRelation);

	/*
	 * 以下生成的所有内容都在 scanCxt 中，或是 scanCxt 的子项，
	 * 所以它们将在 gistendscan 中自动消失。
	 */
	fc_oldCxt = MemoryContextSwitchTo(fc_giststate->scanCxt);

	/* 初始化不透明数据 */
	fc_so = (GISTScanOpaque) palloc0(sizeof(GISTScanOpaqueData));
	fc_so->giststate = fc_giststate;
	fc_giststate->tempCxt = createTempGistContext();
	fc_so->queue = NULL;
	fc_so->queueCxt = fc_giststate->scanCxt;	/* 参考 gistrescan */

	/* 工作空间大小依赖于 numberOfOrderBys: */
	fc_so->distances = palloc(sizeof(fc_so->distances[0]) * fc_scan->numberOfOrderBys);
	fc_so->qual_ok = true;			/* 当键为零的情况下 */
	if (fc_scan->numberOfOrderBys > 0)
	{
		fc_scan->xs_orderbyvals = palloc0(sizeof(Datum) * fc_scan->numberOfOrderBys);
		fc_scan->xs_orderbynulls = palloc(sizeof(bool) * fc_scan->numberOfOrderBys);
		memset(fc_scan->xs_orderbynulls, true, sizeof(bool) * fc_scan->numberOfOrderBys);
	}

	fc_so->killedItems = NULL;		/* 等待需要时再使用 */
	fc_so->numKilled = 0;
	fc_so->curBlkno = InvalidBlockNumber;
	fc_so->curPageLSN = InvalidXLogRecPtr;

	fc_scan->opaque = fc_so;

	/*
	 * 在 gistrescan 中初始化所有索引唯一扫描所需的字段，
	 * 因为我们尚不知道是否在进行索引唯一扫描。
	 */

	MemoryContextSwitchTo(fc_oldCxt);

	return fc_scan;
}

void gistrescan(IndexScanDesc fc_scan, ScanKey fc_key, int fc_nkeys,
		   ScanKey fc_orderbys, int fc_norderbys)
{
	/* nkeys 和 norderbys 参数被忽略 */
	GISTScanOpaque fc_so = (GISTScanOpaque) fc_scan->opaque;
	bool		fc_first_time;
	int			fc_i;
	MemoryContext fc_oldCxt;

	/* 重新扫描现有的索引扫描 --- 重置状态 */

	/*
	 * 第一次通过时，我们在 scanCxt 中创建搜索队列。
	 * 之后的每次，我们在一个单独的 queueCxt 中创建队列，
	 * 该队列是在第二次调用时创建的，并在后续调用时重置。因此，在
	 * 通常情况下，如果扫描仅重新扫描一次，我们只需将队列放置在 scanCxt 中，而不必支付创建第二个内存
	 * 上下文的开销。如果我们需要多次重新扫描，第一次队列将保持
	 * 不变直到扫描结束；这种小浪费似乎值得在普遍情况下的节省。
	 */
	if (fc_so->queue == NULL)
	{
		/* 第一次通过 */
		Assert(fc_so->queueCxt == fc_so->giststate->scanCxt);
		fc_first_time = true;
	}
	else if (fc_so->queueCxt == fc_so->giststate->scanCxt)
	{
		/* 第二次通过 */
		fc_so->queueCxt = AllocSetContextCreate(fc_so->giststate->scanCxt,
											 "GiST queue context",
											 ALLOCSET_DEFAULT_SIZES);
		fc_first_time = false;
	}
	else
	{
		/* 第三次或更晚的通过 */
		MemoryContextReset(fc_so->queueCxt);
		fc_first_time = false;
	}

	/*
	 * 如果我们正在进行索引唯一扫描，在第一次调用时，还需初始化一个
	 * 行描述符以表示返回的索引元组，并创建一个内存上下文以在扫描期间保存它们。
	 */
	if (fc_scan->xs_want_itup && !fc_scan->xs_hitupdesc)
	{
		int			fc_natts;
		int			fc_nkeyatts;
		int			fc_attno;

		/*
		 * 索引的存储类型可能与被索引的原始数据类型不同，因此我们不能
		 * 仅仅获取索引的元组描述符。而是，使用原始数据类型来构造描述符。
		 */
		fc_natts = RelationGetNumberOfAttributes(fc_scan->indexRelation);
		fc_nkeyatts = IndexRelationGetNumberOfKeyAttributes(fc_scan->indexRelation);
		fc_so->giststate->fetchTupdesc = CreateTemplateTupleDesc(fc_natts);
		for (fc_attno = 1; fc_attno <= fc_nkeyatts; fc_attno++)
		{
			TupleDescInitEntry(fc_so->giststate->fetchTupdesc, fc_attno, NULL,
							   fc_scan->indexRelation->rd_opcintype[fc_attno - 1],
							   -1, 0);
		}

		for (; fc_attno <= fc_natts; fc_attno++)
		{
			/* 从 giststate->tupdesc 获取 opcintype */
			TupleDescInitEntry(fc_so->giststate->fetchTupdesc, fc_attno, NULL,
							   TupleDescAttr(fc_so->giststate->leafTupdesc,
											 fc_attno - 1)->atttypid,
							   -1, 0);
		}
		fc_scan->xs_hitupdesc = fc_so->giststate->fetchTupdesc;

		/* 还需创建一个内存上下文来保存返回的元组 */
		fc_so->pageDataCxt = AllocSetContextCreate(fc_so->giststate->scanCxt,
												"GiST page data context",
												ALLOCSET_DEFAULT_SIZES);
	}

	/* 为搜索队列创建新的空的成对堆 */
	fc_oldCxt = MemoryContextSwitchTo(fc_so->queueCxt);
	fc_so->queue = pairingheap_allocate(fc_pairingheap_GISTSearchItem_cmp, fc_scan);
	MemoryContextSwitchTo(fc_oldCxt);

	fc_so->firstCall = true;

	/* 更新扫描关键字，如果提供了一个新的关键字 */
	if (fc_key && fc_scan->numberOfKeys > 0)
	{
		void	  **fc_fn_extras = NULL;

		/*
		 * 如果这不是第一次通过，保留 fn_extra 指针，
		 * 以便在一致函数使用它们缓存数据时，该数据不会在重新扫描中泄漏。
		 */
		if (!fc_first_time)
		{
			fc_fn_extras = (void **) palloc(fc_scan->numberOfKeys * sizeof(void *));
			for (fc_i = 0; fc_i < fc_scan->numberOfKeys; fc_i++)
				fc_fn_extras[fc_i] = fc_scan->keyData[fc_i].sk_func.fn_extra;
		}

		memmove(fc_scan->keyData, fc_key,
				fc_scan->numberOfKeys * sizeof(ScanKeyData));

		/*
		 * 修改扫描关键字，以便对于所有比较都调用一致性方法。
		 * 原操作符以其策略编号的形式传递给一致性函数，该编号可从
		 * sk_strategy 字段获得，而其子类型可从 sk_subtype 字段获得。
		 *
		 * 接下来，如果任何键为 NULL 且该键未标记 SK_SEARCHNULL/SK_SEARCHNOTNULL，则无法找到任何内容（即，我们假定所有可索引的操作符都是严格的）。
		 */
		fc_so->qual_ok = true;

		for (fc_i = 0; fc_i < fc_scan->numberOfKeys; fc_i++)
		{
			ScanKey		fc_skey = fc_scan->keyData + fc_i;

			/*
			 * 将一致的支持函数复制到 ScanKey 结构中，而不是实现过滤运算符的函数。
			 */
			fmgr_info_copy(&(fc_skey->sk_func),
						   &(fc_so->giststate->consistentFn[fc_skey->sk_attno - 1]),
						   fc_so->giststate->scanCxt);

			/* 如果不是第一次，则恢复之前的 fn_extra 指针 */
			if (!fc_first_time)
				fc_skey->sk_func.fn_extra = fc_fn_extras[fc_i];

			if (fc_skey->sk_flags & SK_ISNULL)
			{
				if (!(fc_skey->sk_flags & (SK_SEARCHNULL | SK_SEARCHNOTNULL)))
					fc_so->qual_ok = false;
			}
		}

		if (!fc_first_time)
			pfree(fc_fn_extras);
	}

	/* 如果给定了新的 order-by 键，则更新 order-by 键 */
	if (fc_orderbys && fc_scan->numberOfOrderBys > 0)
	{
		void	  **fc_fn_extras = NULL;

		/* 如上所述，如果不是第一次，则保留 fn_extra */
		if (!fc_first_time)
		{
			fc_fn_extras = (void **) palloc(fc_scan->numberOfOrderBys * sizeof(void *));
			for (fc_i = 0; fc_i < fc_scan->numberOfOrderBys; fc_i++)
				fc_fn_extras[fc_i] = fc_scan->orderByData[fc_i].sk_func.fn_extra;
		}

		memmove(fc_scan->orderByData, fc_orderbys,
				fc_scan->numberOfOrderBys * sizeof(ScanKeyData));

		fc_so->orderByTypes = (Oid *) palloc(fc_scan->numberOfOrderBys * sizeof(Oid));

		/*
		 * 修改 order-by 键，以便在所有比较中调用 Distance 方法。
		 * 原始运算符以其策略编号的形式传递给 Distance 函数，该编号
		 * 可从 sk_strategy 字段获得，子类型可从 sk_subtype 字段获得。
		 */
		for (fc_i = 0; fc_i < fc_scan->numberOfOrderBys; fc_i++)
		{
			ScanKey		fc_skey = fc_scan->orderByData + fc_i;
			FmgrInfo   *fc_finfo = &(fc_so->giststate->distanceFn[fc_skey->sk_attno - 1]);

			/* 检查我们是否确实有一个距离函数... */
			if (!OidIsValid(fc_finfo->fn_oid))
				elog(ERROR, "missing support function %d for attribute %d of index \"%s\"",
					 GIST_DISTANCE_PROC, fc_skey->sk_attno,
					 RelationGetRelationName(fc_scan->indexRelation));

			/*
			 * 查找原始排序运算符返回的数据类型。GiST 始终对距离函数使用 float8，
			 * 但排序运算符可以是其他任何类型。
			 *
			 * XXX: 只有当排序运算符的结果类型为 float4 或 float8 时，
			 * 距离函数才允许是有损的。否则，我们不知道如何将距离返回给执行器。
			 * 但我们无法在这里检查，因为我们不知道距离函数是否有损，
			 * 直到它第一次返回 *recheck = true。
			 */
			fc_so->orderByTypes[fc_i] = get_func_rettype(fc_skey->sk_func.fn_oid);

			/*
			 * 将距离支持函数复制到 ScanKey 结构，而不是实现排序运算符的函数。
			 */
			fmgr_info_copy(&(fc_skey->sk_func), fc_finfo, fc_so->giststate->scanCxt);

			/* 如果不是第一次，则恢复之前的 fn_extra 指针 */
			if (!fc_first_time)
				fc_skey->sk_func.fn_extra = fc_fn_extras[fc_i];
		}

		if (!fc_first_time)
			pfree(fc_fn_extras);
	}

	/* 任何先前的 xs_hitup 将在上述上下文重置中被 pfree */
	fc_scan->xs_hitup = NULL;
}

void gistendscan(IndexScanDesc fc_scan)
{
	GISTScanOpaque fc_so = (GISTScanOpaque) fc_scan->opaque;

	/*
	 * freeGISTstate 足以清理由 gistbeginscan 创建的所有内容，
	 * 以及如果有单独上下文的 queueCxt。
	 */
	freeGISTstate(fc_so->giststate);
}
